\documentclass[12pt,a4paper]{report}
\usepackage{ctex}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{framed} 
\usepackage{fancybox}
\usepackage{subfigure}              % for \subfigure
\usepackage{float}                  % for \begin{figure}[H]
\usetikzlibrary{positioning}        % for 'below=of'
\usepackage{listings}               % for lstlisting
\usetikzlibrary{shapes.geometric}   % for shapes

\newcounter{pcounter}
\setcounter{pcounter}{1}
\newcommand{\practicestart}{\begin{framed}{练习题\thesection.\thepcounter:\par}\addtocounter{pcounter}{1}}
\newcommand{\practiceend}{\end{framed}}

\newcounter{thinkcounter}
\setcounter{thinkcounter}{1}
\newcommand{\thinkstart}{\noindent\rule[0.25\baselineskip]{\textwidth}{1pt}\par
    思考\thesection.\thethinkcounter:\par\addtocounter{thinkcounter}{1}}
\newcommand{\thinkend}{\par\noindent\rule[0.25\baselineskip]{\textwidth}{1pt}\par}

\title{数据结构与算法学习笔记}
\author{李晓政}
\begin{document}
\maketitle

\chapter{Tree}
\section{表达式树}

遍历方式：
\begin{itemize}
    \item 中序遍历：左，结点，右 $\Rightarrow$ 中缀表达式
	\item 后序遍历：左，右，结点 $\Rightarrow$ 后缀表达式
	\item 先序遍历：结点，左，右 $\Rightarrow$ 前缀表达式
\end{itemize}

\practicestart
    将下面中缀表达式用树表示，并输出它的中缀、后缀、前缀表达式：\par
    $(a+(b*c))+(((d*e)+f)*g)$\par
    \noindent\rule[0.25\baselineskip]{\textwidth}{0.5pt}\par
    提示：不需要考虑运算符的优先级，表达式中的优先级用括号表示。\par
    参考答案：\par
    中缀：$(a+(b*c))+(((d*e)+f)*g)$\par
    后缀：$abc*+de*f+g*+$   \par
    前缀：$++a*bc*+*defg$   \par
    源码：tree\_expression.c，只要生成表达式树之后，各种形式的表达式就很容易生成了，只要处
    理一个结点，其它结点递归处理即可。
    \begin{enumerate}
        \item C语言使用递归时，用结构体可以实现递归函数返回字符串。
        \item C语言函数不能返回数组，但是能返回结构体。数组不是一个数据类型。
        \item c语言不能返回局部变量的指针。
        \item 中缀表达式的优先级处理比较麻烦，而前缀和后缀表达式则没有这个问题
    \end{enumerate}
\practiceend

\practicestart
    将后缀表达式转换成表达式树。例如：$abc*+de*f+g*+$\par
    \noindent\rule[0.5\baselineskip]{\textwidth}{0.5pt}\par
    源码：postfix\_to\_tree.c\par
    后缀转成表达式树的复杂度是$O(n)$，而且利用栈实现代码很简洁。
\practiceend

\practicestart
    把中缀表达式转换成后缀表达式。例如：$a+b*c+(d*e+f)*g$\par
    \noindent\rule[0.5\baselineskip]{\textwidth}{0.5pt}\par
    源码：infix\_to\_postfix.c\par
    通过入栈并按优先级出栈的方法，可以解决二元运算符之间的优先级问题，但是括号比较特殊，不是二
    元运算符，需要特殊处理。
\practiceend

\section{二叉查找树}

\thinkstart
相同的数据，树根确定后，二叉树的结构是确定的么？\par
答：不是确定的，比如：
\begin{figure}[H]
    \subfigure[第一种情况]{
        \begin{tikzpicture}[node distance=3em]
            \tikzstyle {yellow_box} = [draw=black, fill=yellow!50!red, circle,dashed];
            \tikzstyle {green_box} = [draw=black, fill=green!80, circle];
            \node (3) at (0,0) [green_box] {3};
            \node (1) [green_box, below left of = 3] {1};
            \node (2) [green_box, below right of = 1] {2};
            \node (4) [green_box, below right of = 3] {4};
            \node (5) [green_box, below right of = 4] {5};
            \draw [->] (3) -> (1);
            \draw [->] (1) -> (2);
            \draw [->] (3) -> (4);
            \draw [->] (4) -> (5);
        \end{tikzpicture}
    }
    \subfigure[第二种情况]{
        \begin{tikzpicture}[node distance=3em]
            \tikzstyle {yellow_box} = [draw=black, fill=yellow!50!red, circle,dashed];
            \tikzstyle {green_box} = [draw=black, fill=green!80, circle];
            \node (3) at (0,0) [green_box] {3};
            \node (2) [green_box, below left of = 3] {2};
            \node (1) [green_box, below left of = 2] {1};
            \node (4) [green_box, below right of = 3] {4};
            \node (5) [green_box, below right of = 4] {5};
            \draw [->] (3) -> (2);
            \draw [->] (2) -> (1);
            \draw [->] (3) -> (4);
            \draw [->] (4) -> (5);
        \end{tikzpicture}
    }
\end{figure}
\thinkend

\practicestart
给定一个二叉树，编写代码画出它的图像。\par
\noindent\rule[0.5\baselineskip]{\textwidth}{0.5pt}\par
分析：\par
两种方案：
\begin{enumerate}
    \item 遍历时一个一个画
    \item 先算出整体结构，再画
\end{enumerate}
第一种方案难以实现，主要是父结点的位置会随了结点的情况而改变。第二种方案需要
\begin{enumerate}
    \item 计算出树的高度
    \item 树的宽度
    \item 每一个元素的位置
\end{enumerate}

通过计算树的宽和高，解决了父结点受子结点影响的问题。但是还有一个问题，打印是
一行一行的，但是树之间联系总是“父$\rightarrow$子”的。为了解决这个问题，做
一个转换，用数组来表示这个树，实现树里面元素的快速访问。数组下标的关系是：

\begin{tikzpicture}[node distance=2em and 8em]
    \tikzstyle {yellow_box} = [draw=black, fill=yellow!50!red, circle,dashed];
    \tikzstyle {green_box} = [draw=black, fill=green!80,ellipse];
    \node (node) at (0,0) [green_box] {$nodes_{[i]}$};
    \node (lchild)  [green_box, above right = of node] {$nodes_{[2i]}$};
    \node (rchild)  [green_box, below right = of node] {$nodes_{[2i+1]}$};
    \draw [->] (node) -- (lchild.west) node [midway,fill=white] {lchild};
    \draw [->] (node) -- (rchild.west) node [midway,fill=white] {rchild};
\end{tikzpicture}


但是要注意这里的下标$i$应该是从1开始的。

源码：print\_tree.c，结果示例：
\lstset{
 basicstyle=\footnotesize,
 columns=fixed,       
 %numbers=left,                                        % 在左侧显示行号
 %numberstyle=\tiny\color{gray},                       % 设定行号格式
 frame=shadowbox,                                     % 不显示背景边框
 backgroundcolor=\color[RGB]{245,245,244},            % 设定背景颜色
 keywordstyle=\color[RGB]{40,40,255},                 % 设定关键字颜色
 numberstyle=\footnotesize\color{darkgray},           
 commentstyle=\it\color[RGB]{0,96,96},                % 设置代码注释的格式
 stringstyle=\rmfamily\slshape\color[RGB]{128,0,0},   % 设置字符串格式
 showstringspaces=false,                              % 不显示字符串中的空格
 language=c,                                        % 设置语言    
}
\begin{lstlisting}
                            +                                
             ______________/ \______________                 
            *                               +                
     ______/ \______                 ______/ \______         
    g               +               *               a        
                 __/ \__         __/ \__                     
                f       *       c       b                    
                       / \                                   
                      e   d                                
\end{lstlisting}

\practiceend

\chapter{图}
\section{基础知识}
\subsection{基本概念}
一个图由顶点集和边集组成，$G=(V,E)$。其中$V$是边的集合，$E$是顶点的集合。
每一条边就是一个点对$(v,w)$。其中$v,w\in V$

\subsection{图的表示}
\subsubsection{使用二维数组来表示：邻接矩阵}
对于每一条边$(u,v)$，使用$A[u][v]=1$来表示。如果有权，也可以使$A[u][v]$
等于权值。

优点： 非常简单

缺点：空间需求比较大,空间需求为$\Theta(|V|^2)$，适合比较稠密的图，
但是大多数应用都不是稠密的。

\subsubsection{使用邻接表}
对于每一个顶点，使用一个表存放所有邻接的顶点。空间需求是$O(|E| + |V|)$。

\subsection{常用的算法}

\subsubsection{拓扑排序}
如果$v_i$到$v_j$存在一条路径，则排序时$v_j$在$v_i$的后面。

算法主要思想：找到一个没有入边的顶点，然后把它和它的边都删除，再找下一个
没有入边的顶点，一直找完即可。

\subsubsection{最短路径算法}

对于赋权的的最短路径问题，如果有负值圈，则最短路径的结果是不确定的。

目前存在的算法里，找出一个点到另个点的最短路径的复杂度，与找到这个点到所有顶点的
最短距离是一样的。

\begin{enumerate}
    \item 无权最短路径问题: $O(|E|+|V|)$
    \item 有权无负边最短路径问题: $O(|E|log|V|)$
    \item 有权有负边最短路径问题: $O(|E| |V|)$
\end{enumerate}

\section{广度优先搜索}
一层一层的从距离最近的点到最远的点。
\practicestart
    找到下图$v_3$到$v_7$的最短距离:

    \begin{tikzpicture}[node distance=2em and 3em]
        \tikzstyle {green_box} = [draw=black, fill=green!80, circle,dashed];
        \node (v1) at (0,0) [green_box] {$v_1$};
        \node (v2)  [green_box, right = of v1] {$v_2$};
        \node (v3)  [green_box, below left = of v1] {$v_3$};
        \node (v4)  [green_box, right = of v3] {$v_4$};
        \node (v5)  [green_box, right = of v4] {$v_5$};
        \node (v6)  [green_box, below left = of v4] {$v_6$};
        \node (v7)  [green_box, right = of v6] {$v_7$};
        \draw [->] (v1) -- (v2);
        \draw [->] (v1) -- (v4);
        \draw [->] (v2) -- (v5);
        \draw [->] (v2) -- (v4);
        \draw [->] (v3) -- (v1);
        \draw [->] (v3) -- (v6);
        \draw [->] (v4) -- (v3);
        \draw [->] (v4) -- (v5);
        \draw [->] (v4) -- (v6);
        \draw [->] (v4) -- (v7);
        \draw [->] (v5) -- (v7);
        \draw [->] (v6) -- (v7);
    \end{tikzpicture}
    首先要表示这个图。




\practiceend
\section{深度优先搜索}

\end{document}
